package 二分.二分答案;

import org.junit.Test;
import utils.Mock_Data;

import javax.crypto.spec.PSource;
import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/6 10:41
 */
public class 左goole面试题 {
    /*
        https://pan.baidu.com/pfile/video?path=%2Fmsb%2F7%E6%9C%883%E6%97%A5%E5%B7%A6%E8%80%81%E5%B8%88%E3%80%90%E5%A4%A7%E5%8E%82%E7%AE%97%E6%B3%95%E9%A2%98%E3%80%91%2F2023-07-03%2019-51-45.mkv&theme=light&from=home
       给定一个数组arr, 长度n
       表示 n 个服务员. arr[i] 表示每个服务员服务一个人所用的时间
       给定一个正数 m, 表示有 m 个人 正在等待服务, 请问你需要等多久?

       n <= 1000    ,m <= 1000_000_000;
     */

    /*
     二分答案:
     答案 和 条件 具有单调性 (想一想二分)
     check函数 : 是一个 逆推过程, 根据答案 推 条件
     尽量 check函数不要涉及太复杂!

     */

    public long solve(int nums[],int m){

//        long l = 0, r = Arrays.stream(nums).min().getAsInt() * m; // 这是一个模糊的范围, 不是最精确的范围 : 优点: 比较容易确定  . 缺点: 可能会有问题,也可能没有问题!
        long l = 0, r = 1000000000000L; // 这是一个模糊的范围, 不是最精确的范围 : 优点: 比较容易确定  . 缺点: 可能会有问题,也可能没有问题!
        while(l < r){
            long mid = l + r >> 1;
            if(check(nums,mid) < m){   // 这点是最狗的, 你是 m + 1 个人 , 所以限制条件是 m + 1
                l = mid + 1;
            }else {
                r = mid;
            }
        }
        return l;
    }

    /*
     一般check 函数的返回值, 直接就是 条件的 属性
     - 比如: 这里 是服务 客人 m , 那么我们的返回的就是服务客人的数量
     */

    /**
     *
     * @param nums
     * @param val
     * @return 返回的是, 在 val 时间内服务客人的数量
     */
    private long check(int nums[],long val) {
        long ans = 0;
        for(int num : nums){
            ans += val / num;  // 每位服务员服务之间是独立,可以分别计算,所有的服务员都是 val这么多时间
            /*
             要给每个 服务员 在 val时间内服务的人数 + 1
             这一点是比较难一想到的!
             */
        }
        return ans + nums.length;
    }

    /*
        用 堆来模拟这个 服务员 服务客人这个过程, 你会发现非常的巧妙!
        堆中的 每对 [x,y] 都按照 x 进行排序 从小到大, x的意思表示的是: 当前服务员 空闲的 **时间点**
     */

    public long solveByHeap(int nums[],int m){

        PriorityQueue<int[]> service = new PriorityQueue<>((a,b) -> a[0] - b[0]); // 用小跟堆,来模拟这个服务 客人的流程
        for(int num : nums){ // 初始 每个服务员 当前都空闲, 所以都是 0
            service.add(new int[]{0,num});
        }
        // 你就是 第 m + 1 位被服务的
        for(int i = 0;i < m;i++){
            int[] remove = service.remove(); // 领走一个 服务员, 并且把该服务员下次 空闲的时间点, 加入 堆中
            service.add(new int[]{remove[0] + remove[1],remove[1]});
        }
        return service.remove()[0]; // 这就是你被服务的时间点!
    }


    @Test
    public void test(){
        int times = 2000;
        for(int i = 1;i <= times;i++){
            int[] ints = Mock_Data.ramdomArray(10, 100, 1, true);
            int m = (int)(Math.random() * 10000) + 1;
            long ans1 = solveByHeap(ints, m);
            long ans2 = solve(ints, m);
            if(ans1 != ans2){
                System.out.println(Arrays.toString(ints));
                System.out.println("fuck!");
                System.out.println(ans1 + " " + ans2);
            }

        }

    }

}
